import java.util.*;

public class Main {
    /*
    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p || root == q) {//判断当前节点是p或q 是的话当前节点就是最近公共祖先
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null) {//左右子树里有p和q那么当前就是最近公共祖先
            return root;
        }else if(left != null) {//只有左子树中 有p和q 那么当前节点就是最近公共祖先
            return left;
        }else{//只有右子树中 有p和q 那么当前节点就是最近公共祖先
            return right;
        }
    }
    /*
    给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。
    （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> retList = new ArrayList();

        if(root == null) {//当没有时,返回空的二维数组
            return retList;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//把根存入队列中

        while(!queue.isEmpty()) {
            int sz = queue.size();
            List<Integer> cont = new ArrayList<>();
            while(sz > 0) {//原来队列中有几个元素 就弹出几个
                TreeNode cur = queue.poll();
                cont.add(cur.val);
                sz--;
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            retList.add(cont);

        }
        //对二维数组进行逆序
        int left = 0;
        int right = retList.size() - 1;
        while(left < right) {
            List<Integer> cont = retList.get(left);
            retList.set(left,retList.get(right));
            retList.set(right,cont);
            left++;
            right--;
        }

        return retList;

    }

    /*
    给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> retList = new ArrayList();

        if(root == null) {//当没有时,返回空的二维数组
            return retList;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//把根存入队列中

        while(!queue.isEmpty()) {
            int sz = queue.size();
            List<Integer> cont = new ArrayList<>();
            while(sz > 0) {//原来队列中有几个元素 就弹出几个
                TreeNode cur = queue.poll();
                cont.add(cur.val);
                sz--;
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            retList.add(cont);

        }
        return retList;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static void main(String[] args) {

    }
}